home *** CD-ROM | disk | FTP | other *** search
/ SGI Developer Toolbox 6.1 / SGI Developer Toolbox 6.1 - Disc 4.iso / public / fax / src / fax2ps / faxdecode.c < prev    next >
C/C++ Source or Header  |  1994-08-01  |  22KB  |  774 lines
  1. #ifndef lint
  2. static char rcsid[] = "$Header: /usr/people/sam/fax/fax2ps/RCS/faxdecode.c,v 1.18 94/03/02 11:52:52 sam Exp $";
  3. #endif
  4.  
  5. /*
  6.  * Copyright (c) 1991, 1992, 1993, 1994 by Sam Leffler.
  7.  * All rights reserved.
  8.  *
  9.  * This file is provided for unrestricted use provided that this
  10.  * legend is included on all tape media and as a part of the
  11.  * software program in whole or part.  Users may copy, modify or
  12.  * distribute this file at will.
  13.  */
  14. #include "defs.h"
  15. #include "t4.h"
  16. #include "g3states.h"
  17.  
  18. Fax3DecodeState fax;
  19.  
  20. static    int decode1DRow(TIFF*, u_char*, int);
  21. static    int decode2DRow(TIFF*, u_char*, int);
  22. static    void fillspan(char*, int, int);
  23. static    void emitcode(TIFF*, int, int, int);
  24. static    int findspan(u_char**, int, int, u_char*);
  25. static    int finddiff(u_char*, int, int);
  26. extern    void printCode(TIFF*, CodeEntry*);
  27.  
  28. static void
  29. emitcode(TIFF* tif, int dx, int x, int count)
  30. {
  31.     CodeEntry* thisCode;
  32.  
  33.     switch (fax.pass) {
  34.     case 1:    /* count potential code & pair use */
  35.     thisCode = enterCode(x-dx, count);
  36.     thisCode->c.count++;
  37.     if (dopairs) {
  38.         if (fax.lastCode)
  39.         enterPair(fax.lastCode, thisCode)->c.count++;
  40.         fax.lastCode = thisCode;
  41.     }
  42.     break;
  43.     case 2:    /* rescan w/ potential codes */
  44.     thisCode = enterCode(x-dx, count);
  45.     if (fax.lastCode) {
  46.         CodePairEntry* pair = findPair(fax.lastCode, thisCode);
  47.         if (pair) {
  48.         pair->c.count++;
  49.         fax.lastCode = 0;
  50.         } else {
  51.         fax.lastCode->c.count++;
  52.         fax.lastCode = thisCode;
  53.         }
  54.     } else
  55.         fax.lastCode = thisCode;
  56.     break;
  57.     case 3:    /* generate encoded output */
  58.     thisCode = enterCode(x-dx, count);
  59.     if (dopairs) {
  60.         if (fax.lastCode) {
  61.         if (!printPair(tif, fax.lastCode, thisCode)) {
  62.             printCode(tif, fax.lastCode);
  63.             fax.lastCode = thisCode;
  64.         } else
  65.             fax.lastCode = 0;
  66.         } else
  67.         fax.lastCode = thisCode;
  68.     } else
  69.         printCode(tif, thisCode);
  70.     break;
  71.     }
  72. }
  73.  
  74. static u_char bitMask[8] =
  75.     { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };
  76. #define    isBitSet(sp)    ((sp)->b.data & bitMask[(sp)->b.bit])
  77.  
  78. #define    is2DEncoding(tif)    (fax.is2d)
  79. #define    fetchByte(tif, sp)    (fax.cc--, *fax.bp++)
  80.  
  81. #define    BITCASE(b)            \
  82.     case b:                \
  83.     code <<= 1;                \
  84.     if (data & (1<<(7-b))) code |= 1;    \
  85.     len++;                \
  86.     if (code > 0) { bit = b+1; break; }
  87.  
  88. /*
  89.  * Skip over input until an EOL code is found.  The
  90.  * value of len is passed as 0 except during error
  91.  * recovery when decoding 2D data.  Note also that
  92.  * we don't use the optimized state tables to locate
  93.  * an EOL because we can't assume much of anything
  94.  * about our state (e.g. bit position).
  95.  */
  96. static void
  97. skiptoeol(TIFF* tif, int len)
  98. {
  99.     Fax3DecodeState *sp = &fax;
  100.     register int bit = sp->b.bit;
  101.     register int data = sp->b.data;
  102.     int code = 0;
  103.  
  104.     /*
  105.      * Our handling of ``bit'' is painful because
  106.      * the rest of the code does not maintain it as
  107.      * exactly the bit offset in the current data
  108.      * byte (bit == 0 means refill the data byte).
  109.      * Thus we have to be careful on entry and
  110.      * exit to insure that we maintain a value that's
  111.      * understandable elsewhere in the decoding logic.
  112.      */
  113.     if (bit == 0)            /* force refill */
  114.         bit = 8;
  115.     for (;;) {
  116.         switch (bit) {
  117. again:  BITCASE(0);
  118.         BITCASE(1);
  119.         BITCASE(2);
  120.         BITCASE(3);
  121.         BITCASE(4);
  122.         BITCASE(5);
  123.         BITCASE(6);
  124.         BITCASE(7);
  125.         default:
  126.             if (fax.cc <= 0)
  127.                 return;
  128.             data = fetchByte(tif, sp);
  129.             goto again;
  130.         }
  131.         if (len >= 12 && code == EOL)
  132.             break;
  133.         code = len = 0;
  134.     }
  135.     sp->b.bit = bit > 7 ? 0 : bit;    /* force refill */
  136.     sp->b.data = data;
  137. }
  138.  
  139. /*
  140.  * Return the next bit in the input stream.  This is
  141.  * used to extract 2D tag values and the color tag
  142.  * at the end of a terminating uncompressed data code.
  143.  */
  144. static int
  145. nextbit(TIFF* tif)
  146. {
  147.     Fax3DecodeState *sp = &fax;
  148.     int bit;
  149.  
  150.     if (sp->b.bit == 0 && fax.cc > 0)
  151.         sp->b.data = fetchByte(tif, sp);
  152.     bit = isBitSet(sp);
  153.     if (++(sp->b.bit) > 7)
  154.         sp->b.bit = 0;
  155.     return (bit);
  156. }
  157.  
  158. static void
  159. bset(unsigned char* cp, int n, int v)
  160. {
  161.     while (n-- > 0)
  162.         *cp++ = v;
  163. }
  164.  
  165. /*
  166.  * Setup state for decoding a strip.
  167.  */
  168. int
  169. FaxPreDecode(TIFF* tif)
  170. {
  171.     Fax3DecodeState *sp = &fax;
  172.  
  173.     sp->b.bit = 0;            /* force initial read */
  174.     sp->b.data = 0;
  175.     sp->b.tag = G3_1D;
  176.     if (sp->b.refline)
  177.         bset(sp->b.refline, sp->b.rowbytes, sp->b.white ? 0xff : 0x00);
  178.     /*
  179.      * If image has EOL codes, they precede each line
  180.      * of data.  We skip over the first one here so that
  181.      * when we decode rows, we can use an EOL to signal
  182.      * that less than the expected number of pixels are
  183.      * present for the scanline.
  184.      */
  185.     if ((fax.options & FAX3_NOEOL) == 0) {
  186.         skiptoeol(tif, 0);
  187.         if (is2DEncoding(tif))
  188.             /* tag should always be 1D! */
  189.             sp->b.tag = nextbit(tif) ? G3_1D : G3_2D;
  190.     }
  191.     return (1);
  192. }
  193.  
  194. /*
  195.  * Fill a span with ones.
  196.  */
  197. static void
  198. fillspan(register char* cp, register int x, register int count)
  199. {
  200.     static unsigned char masks[] =
  201.         { 0, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xff };
  202.  
  203.     if (count <= 0)
  204.         return;
  205.     cp += x>>3;
  206.     if (x &= 7) {            /* align to byte boundary */
  207.         if (count < 8 - x) {
  208.             *cp++ |= masks[count] >> x;
  209.             return;
  210.         }
  211.         *cp++ |= 0xff >> x;
  212.         count -= 8 - x;
  213.     }
  214.     while (count >= 8) {
  215.         *cp++ = 0xff;
  216.         count -= 8;
  217.     }
  218.     *cp |= masks[count];
  219. }
  220.  
  221. /*
  222.  * Decode the requested amount of data.
  223.  */
  224. int
  225. Fax3DecodeRow(TIFF* tif, int npels)
  226. {
  227.     Fax3DecodeState *sp = &fax;
  228.  
  229.     fax.lastCode = 0;
  230.     while (npels > 0) {
  231.     /* decoding only sets non-zero bits */
  232.     memset(sp->scanline, 0, sp->b.rowbytes);
  233.         if (sp->b.tag == G3_1D) {
  234.             if (!decode1DRow(tif, sp->scanline, sp->b.rowpixels) && fax.cc <= 0)
  235.         break;
  236.         } else {
  237.             if (!decode2DRow(tif, sp->scanline, sp->b.rowpixels) && fax.cc <= 0)
  238.         break;
  239.         }
  240.         if (is2DEncoding(tif)) {
  241.             /*
  242.              * Fetch the tag bit that indicates
  243.              * whether the next row is 1d or 2d
  244.              * encoded.  If 2d-encoded, then setup
  245.              * the reference line from the decoded
  246.              * scanline just completed.
  247.              */
  248.             sp->b.tag = nextbit(tif) ? G3_1D : G3_2D;
  249.             if (sp->b.tag == G3_2D)
  250.                 memcpy(sp->b.refline, sp->scanline, sp->b.rowbytes);
  251.         }
  252.         npels -= sp->b.rowpixels;
  253.     fax.row++;
  254.     }
  255.     switch (sp->pass) {
  256.     case 2:
  257.     if (fax.lastCode)
  258.         fax.lastCode->c.count++;
  259.     break;
  260.     case 3:
  261.     if (fax.lastCode)
  262.         printCode(tif, fax.lastCode);
  263.     break;
  264.     }
  265.     return (npels == 0);
  266. }
  267.  
  268. int
  269. Fax4DecodeRow(TIFF* tif, int npels)
  270. {
  271.     Fax3DecodeState *sp = &fax;
  272.  
  273.     fax.lastCode = 0;
  274.     while (npels > 0) {
  275.     /* decoding only sets non-zero bits */
  276.     memset(sp->scanline, 0, sp->b.rowbytes);
  277.     if (!decode2DRow(tif, sp->scanline, sp->b.rowpixels))
  278.         return (0);
  279.     memcpy(sp->b.refline, sp->scanline, sp->b.rowbytes);
  280.     fax.row++;
  281.         npels -= sp->b.rowpixels;
  282.     }
  283.     switch (sp->pass) {
  284.     case 2:
  285.     if (fax.lastCode)
  286.         fax.lastCode->c.count++;
  287.     break;
  288.     case 3:
  289.     if (fax.lastCode)
  290.         printCode(tif, fax.lastCode);
  291.     break;
  292.     }
  293.     return (1);
  294. }
  295.  
  296. /*
  297.  * Decode a run of white.
  298.  */
  299. static int
  300. decode_white_run(TIFF* tif)
  301. {
  302.     Fax3DecodeState *sp = &fax;
  303.     short state = sp->b.bit;
  304.     short action;
  305.     int runlen = 0;
  306.  
  307.     for (;;) {
  308.         if (sp->b.bit == 0) {
  309.     nextbyte:
  310.             if (fax.cc <= 0)
  311.                 return (G3CODE_EOF);
  312.             sp->b.data = fetchByte(tif, sp);
  313.         }
  314.         action = TIFFFax1DAction[state][sp->b.data];
  315.         state = TIFFFax1DNextState[state][sp->b.data];
  316.         if (action == ACT_INCOMP)
  317.             goto nextbyte;
  318.         if (action == ACT_INVALID)
  319.             return (G3CODE_INVALID);
  320.         if (action == ACT_EOL)
  321.             return (G3CODE_EOL);
  322.         sp->b.bit = state;
  323.         action = RUNLENGTH(action - ACT_WRUNT);
  324.         runlen += action;
  325.         if (action < 64)
  326.             return (runlen);
  327.     }
  328.     /*NOTREACHED*/
  329. }
  330.  
  331. /*
  332.  * Decode a run of black.
  333.  */
  334. static int
  335. decode_black_run(TIFF* tif)
  336. {
  337.     Fax3DecodeState *sp = &fax;
  338.     short state = sp->b.bit + 8;
  339.     short action;
  340.     int runlen = 0;
  341.  
  342.     for (;;) {
  343.         if (sp->b.bit == 0) {
  344.     nextbyte:
  345.             if (fax.cc <= 0)
  346.                 return (G3CODE_EOF);
  347.             sp->b.data = fetchByte(tif, sp);
  348.         }
  349.         action = TIFFFax1DAction[state][sp->b.data];
  350.         state = TIFFFax1DNextState[state][sp->b.data];
  351.         if (action == ACT_INCOMP)
  352.             goto nextbyte;
  353.         if (action == ACT_INVALID)
  354.             return (G3CODE_INVALID);
  355.         if (action == ACT_EOL)
  356.             return (G3CODE_EOL);
  357.         sp->b.bit = state;
  358.         action = RUNLENGTH(action - ACT_BRUNT);
  359.         runlen += action;
  360.         if (action < 64)
  361.             return (runlen);
  362.         state += 8;
  363.     }
  364.     /*NOTREACHED*/
  365. }
  366.  
  367. /*
  368.  * Process one row of 1d Huffman-encoded data.
  369.  */
  370. static int
  371. decode1DRow(TIFF* tif, u_char* buf, int npels)
  372. {
  373.     Fax3DecodeState *sp = &fax;
  374.     int x = 0;
  375.     int dx = 0;
  376.     int runlen;
  377.     short action;
  378.     short color = sp->b.white;
  379.     static char module[] = "Fax3Decode1D";
  380.  
  381.     for (;;) {
  382.         if (color == sp->b.white)
  383.             runlen = decode_white_run(tif);
  384.         else
  385.             runlen = decode_black_run(tif);
  386.         switch (runlen) {
  387.         case G3CODE_EOF:
  388.             TIFFError(module,
  389.                 "%s: Premature EOF at scanline %d (x %d)",
  390.                 TIFFFileName(tif), fax.row, x);
  391.             return (0);
  392.         case G3CODE_INVALID:    /* invalid code */
  393.             /*
  394.              * An invalid code was encountered.
  395.              * Flush the remainder of the line
  396.              * and allow the caller to decide whether
  397.              * or not to continue.  Note that this
  398.              * only works if we have a G3 image
  399.              * with EOL markers.
  400.              */
  401.             TIFFError(TIFFFileName(tif),
  402.                "%s: Bad code word at scanline %d (x %d)",
  403.                module, fax.row, x);
  404.             goto done;
  405.         case G3CODE_EOL:    /* premature end-of-line code */
  406.             TIFFWarning(TIFFFileName(tif),
  407.                 "%s: Premature EOL at scanline %d (x %d)",
  408.                 module, fax.row, x);
  409.             return (1);    /* try to resynchronize... */
  410.         }
  411.         if (x+runlen > npels)
  412.             runlen = npels-x;
  413.         if (runlen > 0) {
  414.             if (color)
  415.                 fillspan((char *)buf, x, runlen);
  416.         if (color != sp->b.white) {
  417.         emitcode(tif, dx, x, runlen);
  418.         dx = x+runlen;
  419.         }
  420.             x += runlen;
  421.             if (x >= npels)
  422.                 break;
  423.         }
  424.         color = !color;
  425.     }
  426. done:
  427.     /*
  428.      * Cleanup at the end of the row.  This convoluted
  429.      * logic is merely so that we can reuse the code with
  430.      * two other related compression algorithms (2 & 32771).
  431.      *
  432.      * Note also that our handling of word alignment assumes
  433.      * that the buffer is at least word aligned.  This is
  434.      * the case for most all versions of malloc (typically
  435.      * the buffer is returned longword aligned).
  436.      */
  437.     if ((fax.options & FAX3_NOEOL) == 0)
  438.         skiptoeol(tif, 0);
  439.     if (fax.options & FAX3_BYTEALIGN)
  440.         sp->b.bit = 0;
  441.     if ((fax.options & FAX3_WORDALIGN) && ((long)fax.bp & 1))
  442.         (void) fetchByte(tif, sp);
  443.     return (x == npels);
  444. }
  445.  
  446. /*
  447.  * Group 3 2d Decoding support.
  448.  */
  449.  
  450. /*
  451.  * Return the next uncompressed mode code word.
  452.  */
  453. static int
  454. decode_uncomp_code(TIFF* tif)
  455. {
  456.     Fax3DecodeState *sp = &fax;
  457.     short code;
  458.  
  459.     do {
  460.         if (sp->b.bit == 0 || sp->b.bit > 7) {
  461.             if (fax.cc <= 0)
  462.                 return (UNCOMP_EOF);
  463.             sp->b.data = fetchByte(tif, sp);
  464.         }
  465.         code = TIFFFaxUncompAction[sp->b.bit][sp->b.data];
  466.         sp->b.bit = TIFFFaxUncompNextState[sp->b.bit][sp->b.data];
  467.     } while (code == ACT_INCOMP);
  468.     return (code);
  469. }
  470.  
  471. /*
  472.  * Process one row of 2d encoded data.
  473.  */
  474. static int
  475. decode2DRow(TIFF* tif, u_char* buf, int npels)
  476. {
  477. #define    PIXEL(buf,ix)    ((((buf)[(ix)>>3]) >> (7-((ix)&7))) & 1)
  478.     Fax3DecodeState *sp = &fax;
  479.     int a0 = 0;
  480.     int b1 = 0;
  481.     int b2 = 0;
  482.     int dx = 0;
  483.     int run1, run2;        /* for horizontal mode */
  484.     short mode;
  485.     short color = sp->b.white;
  486.     static char module[] = "Fax3Decode2D";
  487.  
  488.     do {
  489.         if (sp->b.bit == 0 || sp->b.bit > 7) {
  490.             if (fax.cc <= 0) {
  491.                 TIFFError(module,
  492.                 "%s: Premature EOF at scanline %d",
  493.                     TIFFFileName(tif), fax.row);
  494.                 return (0);
  495.             }
  496.             sp->b.data = fetchByte(tif, sp);
  497.         }
  498.         mode = TIFFFax2DMode[sp->b.bit][sp->b.data];
  499.         sp->b.bit = TIFFFax2DNextState[sp->b.bit][sp->b.data];
  500.         switch (mode) {
  501.         case MODE_NULL:
  502.             break;
  503.         case MODE_PASS:
  504.             if (a0 || PIXEL(sp->b.refline, 0) == color) {
  505.                 b1 = finddiff(sp->b.refline, a0, npels);
  506.                 if (color == PIXEL(sp->b.refline, b1))
  507.                     b1 = finddiff(sp->b.refline, b1, npels);
  508.             } else
  509.                 b1 = 0;
  510.             b2 = finddiff(sp->b.refline, b1, npels);
  511.             if (color)
  512.                 fillspan((char *)buf, a0, b2 - a0);
  513.         if (color != sp->b.white) {
  514.         emitcode(tif, dx, a0, b2 - a0);
  515.         dx = b2;
  516.         }
  517.             a0 += b2 - a0;
  518.             break;
  519.         case MODE_HORIZ:
  520.             if (color == sp->b.white) {
  521.                 run1 = decode_white_run(tif);
  522.                 run2 = decode_black_run(tif);
  523.             } else {
  524.                 run1 = decode_black_run(tif);
  525.                 run2 = decode_white_run(tif);
  526.             }
  527.         /*
  528.          * Do the appropriate fill.  Note that we exit
  529.          * this logic with the same color that we enter
  530.          * with since we do 2 fills.  This explains the
  531.          * somewhat obscure logic below.
  532.          */
  533.         if (run1 < 0)
  534.         goto bad;
  535.         if (a0 + run1 > npels)
  536.         run1 = npels - a0;
  537.         if (color)
  538.         fillspan((char *)buf, a0, run1);
  539.         if (color != sp->b.white) {
  540.         emitcode(tif, dx, a0, run1);
  541.         dx = a0 + run1;
  542.         }
  543.         a0 += run1;
  544.         if (run2 < 0)
  545.         goto bad;
  546.         if (a0 + run2 > npels)
  547.         run2 = npels - a0;
  548.         if (!color)
  549.         fillspan((char *)buf, a0, run2);
  550.         if (!color != sp->b.white) {
  551.         emitcode(tif, dx, a0, run2);
  552.         dx = a0 + run2;
  553.         }
  554.         a0 += run2;
  555.             break;
  556.         case MODE_VERT_V0:
  557.         case MODE_VERT_VR1:
  558.         case MODE_VERT_VR2:
  559.         case MODE_VERT_VR3:
  560.         case MODE_VERT_VL1:
  561.         case MODE_VERT_VL2:
  562.         case MODE_VERT_VL3:
  563.             /*
  564.              * Calculate b1 as the "first changing element
  565.              * on the reference line to right of a0 and of
  566.              * opposite color to a0".  In addition, "the
  567.              * first starting picture element a0 of each
  568.              * coding line is imaginarily set at a position
  569.              * just before the first picture element, and
  570.              * is regarded as a white element".  For us,
  571.              * the condition (a0 == 0 && color == sp->b.white)
  572.              * describes this initial condition. 
  573.              */
  574.             if (!(a0 == 0 &&
  575.         color == sp->b.white && PIXEL(sp->b.refline, 0) != sp->b.white)) {
  576.                 b1 = finddiff(sp->b.refline, a0, npels);
  577.                 if (color == PIXEL(sp->b.refline, b1))
  578.                     b1 = finddiff(sp->b.refline, b1, npels);
  579.             } else
  580.                 b1 = 0;
  581.             b1 += mode - MODE_VERT_V0;
  582.             if (color)
  583.                 fillspan((char *)buf, a0, b1 - a0);
  584.         if (color != sp->b.white) {
  585.         emitcode(tif, dx, a0, b1 - a0);
  586.         dx = b1;
  587.         }
  588.             color = !color;
  589.             a0 += b1 - a0;
  590.             break;
  591.     case MODE_UNCOMP:
  592.             /*
  593.              * Uncompressed mode: select from the
  594.              * special set of code words.
  595.              */
  596.             do {
  597.                 mode = decode_uncomp_code(tif);
  598.                 switch (mode) {
  599.                 case UNCOMP_RUN1:
  600.                 case UNCOMP_RUN2:
  601.                 case UNCOMP_RUN3:
  602.                 case UNCOMP_RUN4:
  603.                 case UNCOMP_RUN5:
  604.                     run1 = mode - UNCOMP_RUN0;
  605.                     fillspan((char *)buf, a0+run1-1, 1);
  606.                     a0 += run1;
  607.             if (color != sp->b.white) {
  608.             emitcode(tif, dx, a0-1, 1);
  609.             dx = a0;
  610.             }
  611.                     break;
  612.                 case UNCOMP_RUN6:
  613.                     a0 += 5;
  614.                     break;
  615.                 case UNCOMP_TRUN0:
  616.                 case UNCOMP_TRUN1:
  617.                 case UNCOMP_TRUN2:
  618.                 case UNCOMP_TRUN3:
  619.                 case UNCOMP_TRUN4:
  620.                     run1 = mode - UNCOMP_TRUN0;
  621.                     a0 += run1;
  622.                     color = nextbit(tif) ? !sp->b.white : sp->b.white;
  623.                     break;
  624.                 case UNCOMP_INVALID:
  625.                     TIFFError(module,
  626.                 "%s: Bad uncompressed code word at scanline %d",
  627.                         TIFFFileName(tif), fax.row);
  628.                     goto bad;
  629.                 case UNCOMP_EOF:
  630.                     TIFFError(module,
  631.                         "%s: Premature EOF at scanline %d",
  632.                         TIFFFileName(tif), fax.row);
  633.                     return (0);
  634.                 }
  635.             } while (mode < UNCOMP_EXIT);
  636.             break;
  637.     case MODE_ERROR_1:
  638.             if ((fax.options & FAX3_NOEOL) == 0) {
  639.                 TIFFWarning(TIFFFileName(tif),
  640.                     "%s: Premature EOL at scanline %d (x %d)",
  641.                     module, fax.row, a0);
  642.                 skiptoeol(tif, 7);    /* seen 7 0's already */
  643.                 return (1);        /* try to synchronize */
  644.             }
  645.             /* fall thru... */
  646.     case MODE_ERROR:
  647.             TIFFError(TIFFFileName(tif),
  648.                 "%s: Bad 2D code word at scanline %d",
  649.                 module, fax.row);
  650.             goto bad;
  651.     default:
  652.             TIFFError(TIFFFileName(tif),
  653.                 "%s: Panic, bad decoding state at scanline %d",
  654.                 module, fax.row);
  655.             return (0);
  656.         }
  657.     } while (a0 < npels);
  658. bad:
  659.     /*
  660.      * Cleanup at the end of row.  We check for
  661.      * EOL separately so that this code can be
  662.      * reused by the Group 4 decoding routine.
  663.      */
  664.     if ((fax.options & FAX3_NOEOL) == 0)
  665.         skiptoeol(tif, 0);
  666.     return (a0 >= npels);
  667. #undef    PIXEL
  668. }
  669.  
  670. static u_char zeroruns[256] = {
  671.     8, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4,    /* 0x00 - 0x0f */
  672.     3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,    /* 0x10 - 0x1f */
  673.     2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,    /* 0x20 - 0x2f */
  674.     2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,    /* 0x30 - 0x3f */
  675.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    /* 0x40 - 0x4f */
  676.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    /* 0x50 - 0x5f */
  677.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    /* 0x60 - 0x6f */
  678.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    /* 0x70 - 0x7f */
  679.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x80 - 0x8f */
  680.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x90 - 0x9f */
  681.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0xa0 - 0xaf */
  682.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0xb0 - 0xbf */
  683.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0xc0 - 0xcf */
  684.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0xd0 - 0xdf */
  685.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0xe0 - 0xef */
  686.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0xf0 - 0xff */
  687. };
  688. static u_char oneruns[256] = {
  689.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x00 - 0x0f */
  690.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x10 - 0x1f */
  691.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x20 - 0x2f */
  692.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x30 - 0x3f */
  693.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x40 - 0x4f */
  694.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x50 - 0x5f */
  695.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x60 - 0x6f */
  696.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x70 - 0x7f */
  697.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    /* 0x80 - 0x8f */
  698.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    /* 0x90 - 0x9f */
  699.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    /* 0xa0 - 0xaf */
  700.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    /* 0xb0 - 0xbf */
  701.     2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,    /* 0xc0 - 0xcf */
  702.     2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,    /* 0xd0 - 0xdf */
  703.     3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,    /* 0xe0 - 0xef */
  704.     4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 7, 8,    /* 0xf0 - 0xff */
  705. };
  706.  
  707. /*
  708.  * Bit handling utilities.
  709.  */
  710.  
  711. /*
  712.  * Find a span of ones or zeros using the supplied
  713.  * table.  The byte-aligned start of the bit string
  714.  * is supplied along with the start+end bit indices.
  715.  * The table gives the number of consecutive ones or
  716.  * zeros starting from the msb and is indexed by byte
  717.  * value.
  718.  */
  719. static int
  720. findspan(u_char** bpp, int bs, int be, u_char* tab)
  721. {
  722.     u_char *bp = *bpp;
  723.     int bits = be - bs;
  724.     int n, span;
  725.  
  726.     /*
  727.      * Check partial byte on lhs.
  728.      */
  729.     if (bits > 0 && (n = (bs & 7))) {
  730.     span = tab[(*bp << n) & 0xff];
  731.     if (span > 8-n)        /* table value too generous */
  732.         span = 8-n;
  733.     if (n+span < 8)        /* doesn't extend to edge of byte */
  734.         goto done;
  735.     bits -= span;
  736.     bp++;
  737.     } else
  738.     span = 0;
  739.     /*
  740.      * Scan full bytes for all 1's or all 0's.
  741.      */
  742.     while (bits >= 8) {
  743.     n = tab[*bp];
  744.     span += n;
  745.     bits -= n;
  746.     if (n < 8)        /* end of run */
  747.         goto done;
  748.     bp++;
  749.     }
  750.     /*
  751.      * Check partial byte on rhs.
  752.      */
  753.     if (bits > 0) {
  754.     n = tab[*bp];
  755.     span += (n > bits ? bits : n);
  756.     }
  757. done:
  758.     *bpp = bp;
  759.     return (span);
  760. }
  761.  
  762. /*
  763.  * Return the offset of the next bit in the range
  764.  * [bs..be] that is different from bs.  The end,
  765.  * be, is returned if no such bit exists.
  766.  */
  767. static int
  768. finddiff(u_char* cp, int bs, int be)
  769. {
  770.     cp += bs >> 3;            /* adjust byte offset */
  771.     return (bs + findspan(&cp, bs, be,
  772.     (*cp & (0x80 >> (bs&7))) ? oneruns : zeroruns));
  773. }
  774.